#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;

typedef int Vertex; /* 顶点编号类型 */
typedef char VertInfo; /* 顶点信息类型 */

typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest; /* 边的另一端点编号 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj; /* 邻接表头指针 */
    VertInfo data; /* 存储顶点信息 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed; /* true为有向图，false为无向图 */
};

typedef struct EulerNode *ECList; /* 欧拉回路链表 */
struct EulerNode {
    Vertex ver; /* 顶点编号 */
    ECList next; /* 线性表中下一个元素的位置 */
};
typedef struct CircPtrNode *Circuit; /* 欧拉回路 */
struct CircPtrNode {
    ECList first; /* 回路首结点指针 */
    ECList last; /* 回路尾结点指针 */
};

void InitGraph(LGraph graph, int kMaxVertex, bool directed) {
    /* 初始化一个空的图 */
    Vertex v;
    Position p;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明邻接表头结点数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (AdjList *)malloc(sizeof(AdjList) * kMaxVertex);
    for (v = 0; v < kMaxVertex; v++) {
        graph->ver_list[v] = (AdjList)malloc(sizeof(struct HeadNode));
        graph->ver_list[v]->adj = NULL;
    }
    graph->directed = directed;
}

void InsertEdge(LGraph graph, Vertex u, Vertex v) {
    Position p;

    p = (Position)malloc(sizeof(struct EdgeNode));
    p->dest = v;
    p->next = graph->ver_list[u]->adj;
    graph->ver_list[u]->adj = p;
    graph->m_edges++;
    if (graph->directed ==
                false) { /* 如果是无向图，还要将u插入v的边表中 */
        p = (Position)malloc(sizeof(struct EdgeNode));
        p->dest = u;
        p->next = graph->ver_list[v]->adj;
        graph->ver_list[v]->adj = p;
    }
}

int *dfn, *low, count;
Vertex *parents;
bool *visited, *points;

int Min(int x, int y) {
    return (x < y) ? x : y;
}

/* 算法7-22：利用深度优先遍历计算dfn和low的值 DfnAndLow(graph,v,parent) */
void DfnAndLow(LGraph graph, Vertex v, Vertex parent) {
    Position p;

    visited[v] = true;
    dfn[v] = count;
    low[v] = count;
    parents[v] = parent;
    count++;
    p = graph->ver_list[v]->adj; /* 沿v向下搜索 */
    while (p != NULL) {
        if (visited[p->dest] == false) {
            DfnAndLow(graph, p->dest, v);
            low[v] = Min(low[v], low[p->dest]);
        } else {
            if (p->dest != parent) {
                low[v] = Min(low[v], dfn[p->dest]);
            }
        }
        p = p->next;
    }
}
/* 算法7-22 结束 */

/* 算法7-23：求割点的Tarjan算法 ArticulationPoint (graph, start) */
void ArticulationPoint(LGraph graph, Vertex start) {
    Vertex v;
    int n_child;

    for (v = 0; v < graph->n_verts; v++) {
        visited[v] = false; /* 初始化各顶点的访问标志为未访问 */
        points[v] = false; /* 初始化各顶点都不是割点 */
    }
    DfnAndLow(graph, start, -1);
    n_child = 0; /* 对根结点的孩子结点计数 */
    for (v = 0; v < graph->n_verts; v++) {
        if (parents[v] != -1) { /* 若v不是根结点 */
            if (parents[v] == start) {
                n_child++;
            } else {
                if (low[v] >= dfn[parents[v]]) { /* 记录割点 */
                    points[parents[v]] = true;
                }
            }
        }
    }
    if (n_child >= 2) { /* 判断根结点是否割点 */
        points[start] = true; /* 记录割点 */
    }
}
/* 算法7-23 结束 */

/* 算法7-24：求割边的Tarjan算法 ArticulationEdge(graph, start) */
void ArticulationEdge(LGraph graph, Vertex start) {
    Vertex v;
    VertInfo head, tail;

    for (v = 0; v < graph->n_verts; v++) {
        visited[v] = false; /* 初始化各顶点的访问标志为未访问 */
    }
    DfnAndLow(graph, start, -1);
    for (v = 0; v < graph->n_verts; v++) {
        if (parents[v] != -1) { /* 若v不是根结点 */
            if (low[v] > dfn[parents[v]]) { /* 打印割边 */
                head = graph->ver_list[parents[v]]->data;
                tail = graph->ver_list[v]->data;
                printf("(%c, %c)\n", head, tail);
            }
        }
    }
}
/* 算法7-24 结束 */

LGraph BuildGraph() {
    LGraph graph;
    int kMaxVertex, n, m, i;
    Vertex u, v;

    scanf("%d\n", &kMaxVertex);
    graph = (LGraph)malloc(sizeof(struct LGraphNode));
    InitGraph(graph, kMaxVertex, false);
    scanf("%d %d\n", &n, &m);
    for (v = 0; v < n; v++) {
        scanf("%c ", &graph->ver_list[v]->data);
        graph->n_verts++;
    }
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        InsertEdge(graph, u, v);
    }
    return graph;
}

int main(void) {
    LGraph graph;
    Vertex v;

    graph = BuildGraph();
    dfn = (int *)malloc(sizeof(int) * graph->n_verts);
    low = (int *)malloc(sizeof(int) * graph->n_verts);
    parents = (Vertex *)malloc(sizeof(Vertex) * graph->n_verts);
    visited = (bool *)malloc(sizeof(bool) * graph->n_verts);
    count = 0;
    points = (bool *)malloc(sizeof(bool) * graph->n_verts);
    ArticulationPoint(graph, 0);
    for (v = 0; v < graph->n_verts; v++) {
        if (points[v] == true) {
            printf("%c", graph->ver_list[v]->data);
        }
    }
    printf("\n");
    ArticulationEdge(graph, 0);

    return 0;
}